/**
 * 
 */
package interval.passed;

import java.util.ArrayList;

/**
 * @author xyyi
 *
 */
public class InsertInterval {

	/**
	Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).

	You may assume that the intervals were initially sorted according to their start times.

	Example 1:
	Given intervals [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].

	Example 2:
	Given [1,2],[3,5],[6,7],[8,10],[12,16], insert and merge [4,9] in as [1,2],[3,10],[12,16].

	This is because the new interval [4,9] overlaps with [3,5],[6,7],[8,10].
	 */
	public ArrayList<Interval> insert(ArrayList<Interval> intervals,
			Interval newInterval) {
		ArrayList<Interval> result = new ArrayList<Interval>();
		if (intervals == null)
			return result;

		int start = newInterval.start;
		int end = newInterval.end;
		boolean inserted = false;
		for (int i = 0; i < intervals.size(); i++) {
			if (intervals.get(i).end < start) {
				result.add(intervals.get(i));
			} else if (intervals.get(i).start > end) {
				if (!inserted) {
					result.add(new Interval(start, end));
					inserted = true;
				}
				result.add(intervals.get(i));
			} else {
				start = Math.min(start, intervals.get(i).start);
				end = Math.max(end, intervals.get(i).end);
			}
		}
		if (!inserted)
			result.add(new Interval(start, end));

		return result;
	}

	/**
	 * Definition for an interval.
	 */
	public class Interval {
		int start;
		int end;

		Interval() {
			start = 0;
			end = 0;
		}

		Interval(int s, int e) {
			start = s;
			end = e;
		}
	}

	/**
	 * 
	 */
	public InsertInterval() {
		// TODO Auto-generated constructor stub
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

}
